package com.LeetCode.dp.package_01;

import org.junit.Test;

/**
 * 最后一块石头的重量 Ⅱ
 */
public class lastStoneWeight {
    public int lastStoneWeightII(int[] stones) {
        int len = stones.length;
        if(len == 0) return 0;

        int sum = 0;
        for(int stone : stones){
            sum += stone;
        }

        int[][] dp = new int[len+1][sum/2 + 1];

        for(int i = 1; i<len + 1; i++){
            for(int j = 1; j<sum/2 + 1; j++){
                if(stones[i-1] <= j){
                    //是否放入第 i - 1个石块
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j - stones[i-1]] + stones[i-1]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        return sum - 2 * dp[len][sum / 2];
    }

    @Test
    public void test(){
        int[] arr = {2,7,4,1,8,1};
        System.out.println(lastStoneWeightII(arr));
    }
}
